/**
 * https://leetcode-cn.com/problems/construct-string-from-binary-tree/
 * 二叉树转字符串
 * @param root 
 */
const tree2str = (root: TreeNode | null): string => {
    const ans: string[] = []
    /**
     * 前序遍历
     * @param n 
     */
    const preOrder = (n: TreeNode | null) => {
        // 为空, 直接返回
        if (n === null) return

        ans.push(n.val + '')

        // 左孩子或者右孩子不为空
        if (n.left !== null || n.right !== null) {
            // 进来只有两种可能, 左孩子不为空 || 左孩子为空, 右孩子不为空
            ans.push('(')
            preOrder(n.left);
            ans.push(')')
        }

        // 右孩子不为空
        if (n.right !== null) {
            ans.push('(')
            preOrder(n.right);
            ans.push(')')
        }

    }
    preOrder(root)


    // 去掉最后一个括号
    return ans.join('')
};

const tree2str2 = (root: TreeNode | null): string => {
    if (root === null) return '';
    let ans = ''

    /**
     * 前序遍历
     * @param n 
     */
    const preOrder = (n: TreeNode) => {
        // 加上该值
        ans += n.val

        // 遍历左节点之前加上(
        if (n.left) {
            ans += '('
            // 遍历左子树
            preOrder(n.left)
        } else if (n.right !== null) {
            // 右孩子不为空, 加上()
            ans += '()'
        }

        if (n.right) {
            ans += '('
            // 遍历右子树
            preOrder(n.right);
        } 


        // 遍历完右节点后加上)
        ans += ')'
    }
    preOrder(root)
    // 去掉最后一个括号
    return ans.slice(0, -1)
};


const tree2str3 = (root: TreeNode | null): string => {
    if (root === null) return '';
    let ans = ''

    /**
     * 检查右孩子是否为空, 为空, 把括号截掉
     * @returns 
     */
    const check = () => {
        const len = ans.length;
        if (len >= 2 && ans[len - 1] === ')' && ans[len - 2] === '(') {
            // 为空, 截掉最后的两个括号
            ans = ans.slice(0, -2)
        }
    }

    /**
     * 前序遍历
     * @param n 
     */
    const preOrder = (n: TreeNode) => {
        // 加上该值
        ans += n.val

        // 遍历左节点之前加上(
        if (n.left) {
            ans += '('
            // 遍历左子树
            preOrder(n.left)
        } else {
            ans += '()'
        }

        if (n.right) {
            ans += '('
            // 遍历右子树
            preOrder(n.right);
        } else {
            // 右孩子为空, 检查左孩子是否需要删除
            check()
        }


        // 遍历完右节点后加上)
        ans += ')'
    }
    preOrder(root)
    // 去掉最后一个括号
    return ans.slice(0, -1)
};
